package collection.MyTree;

import com.sun.security.jgss.GSSUtil;

import java.util.*;

public class BinaryTree {
    static  class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public TreeNode root;//指向根结点

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        TreeNode I =new TreeNode('I');
        TreeNode J = new TreeNode('J');
        A.left = B;
        B.left = E;
        E.right = F;
        B.right = C;
        C.left = G;
        C.right = D;
        D.left = H;
        H.right = I;
        I.right = J;

        return A;
    }
    public void  preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 将前序遍历的结果存储到list
     * @param root
     * @return
     */
    public List<TreeNode> preOrderList(TreeNode root){
        List<TreeNode> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        list.add(root);
        list.addAll(preOrderList(root.left));
        list.addAll(preOrderList(root.right));
        return list;
    }
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    public int nodeSize(TreeNode root){
        if (root == null)
            return 0;
        return nodeSize(root.left) + nodeSize(root.right) + 1;
    }
    public int getLeafSize(TreeNode root){
        if (root == null)
            return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafSize(root.left) + getLeafSize(root.right);
    }
    public int getKLevelNodeCount(TreeNode root,int k){
        if (root == null){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }

    /**
     * 树的最大深度
     * @param root
     * @return
     */
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right)) + 1;
    }
    public boolean find(TreeNode root,char key){
        if (root == null){
            return false;
        }if (root.val == key){
            return true;
        }
        if (find(root.left,key)){
            return true;
        }
        if (find(root.right,key)){
            return true;
        }
        return false;
    }
    public List<List<Character>> levelOrder(TreeNode root){
        List<List<Character>> ret =  new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Character> level = new ArrayList<>();
            while(size != 0){
                TreeNode cur = queue.poll();
                if (cur == null){
                    level.add(null);
                }else {
                    level.add(cur.val);
                }
                if (cur != null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }


                size--;
            }
            ret.add(level);
        }
        return ret;
    }
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root == null){
            return null;
        }
        if (root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if (leftTree != null && rightTree != null){
            return root;
        }else if (leftTree != null){
            return leftTree;
        }else {
            return rightTree;
        }
    }
    public TreeNode lowestCommonAncestorStack(TreeNode root,TreeNode p,TreeNode q){
        if (root == null){
            return null;
        }
        Stack<TreeNode> pStack = new Stack<>();
        getPath(root,p,pStack);
        Stack<TreeNode> qStack = new Stack<>();
        getPath(root,q,qStack);
        int sizeP = pStack.size();
        int sizeQ = qStack.size();
        if (sizeQ > sizeP){
            equlesStack(qStack,sizeQ,sizeP);
        }else {
            equlesStack(pStack,sizeP,sizeQ);
        }
        while(!pStack.isEmpty() && !qStack.isEmpty()){
            if (pStack.peek() == qStack.peek()){
                return pStack.peek();
            }
            pStack.pop();
            qStack.pop();
        }
        return null;
    }
    private void equlesStack(Stack<TreeNode> stack,int sizeX,int sizeY){
        int size = sizeX - sizeY;
        while (size != 0){
            stack.pop();
            size--;
        }
    }
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if (root == null || node == null){
            return false;
        }
        stack.add(root);
        if (root == node){
            return true;
        }
        boolean leftFlg = getPath(root.left,node,stack);
        if (leftFlg){
            return true;
        }
        boolean rightFlg = getPath(root.right,node,stack);
        if (rightFlg){
            return true;
        }
        stack.pop();
        return false;
    }
}
